package net.projecteuler.prob;

public class Problem31 implements Runnable{

	int[] coins = {200, 100, 50, 20, 10, 5, 2, 1};
	
	@Override
	public void run() {
		System.out.println(count(200, 0));
	}
	
	public int count(int tot, int coinIdx){
		if(coinIdx == coins.length - 1)
			return (tot % coins[coinIdx] == 0) ? 1 : 0;
		
		int remainder = tot;
		int sum = 0;
		int coin = coins[coinIdx];
		while(true){
			sum += count(remainder, coinIdx + 1);
			remainder -= coin;
			if(remainder == 0){
				sum += 1;
				break;
			} else if (remainder < 0) {
				break;
			}
		}
		
		return sum;
	}
}
